package other

import (
	"math"
	"sort"
)

//计算x的平方根

func mySqrt(x int) int {
	l, r := 0, x
	ans := -1
	for l <= r {
		mid := l + (r-l)/2
		if mid*mid <= x {
			ans = mid
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return ans
}

/**
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

*/
func mergeBound(intervals [][]int) [][]int {
	if len(intervals) < 2 {
		return intervals
	}
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] > intervals[j][0] {
			return false
		}
		return true
	})
	//两两合并
	var result [][]int //模拟栈，每次和栈顶的数据进行区间比较进行合并
	for i := 0; i < len(intervals); i++ {
		L := intervals[i][0]
		R := intervals[i][1]
		if len(result) == 0 || result[len(result)-1][1] < L {
			//前缀区间相同
			result = append(result, []int{L, R})
		} else {
			//前缀区间不同，比较后缀区间的大小是否包含
			result[len(result)-1][1] = max(R, result[len(result)-1][1])
		}
	}
	return result
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/**
两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
*/

func divide(dividend int, divisor int) int {
	if divisor == 1 {
		return dividend
	}
	negetive := false
	if dividend == 0 {
		return 0
	}
	if (dividend < 0 && divisor > 0) || (divisor < 0 && dividend > 0) {
		negetive = true
	}
	//转换正数进行计算
	if divisor < 0 {
		divisor = -divisor
	}
	if dividend < 0 {
		dividend = -dividend
	}
	//递归+倍增法
	var div func(a, b int) int
	div = func(dividend, divisor int) int {
		a := dividend
		b := divisor
		if a < b {
			return 0
		} //a<b 商只能是0
		count := 1
		for (b + b) <= a { //倍增：如果加倍后<b，继续倍增
			b = b + b
			count = count + count
		}
		return count + div(a-b, divisor) //差值递归进行 div计算
	}
	res := div(dividend, divisor)
	if !negetive {
		if res > math.MaxInt32 {
			res = math.MaxInt32 //边界控制
		}
	} else {
		res = -res
	}
	return res

}
